package com.kimari.demo;

/**
 * 算法练习八
 * 求任意两个正整数的最大公约数和(GCD)和最小公倍数(LCM)
 * 辗转相除法的算法为：首先将 m 除以 n（m>n）得余数 r，
 * 再用余数r 去除原来的除数，得新的余数，重复此过程直到
 * 余数为 0时停止，此时的除数就是 m 和 n 的最大公约数。
 * 求 m 和 n 的最小公倍数: m 和 n 的积除以( m 和 n 的最大公约数)。
 *
 * @author kimariyb
 */
public class GcdLcm {
    /**
     * @param numOne 第一个数
     * @param numTwo 第二个数
     * @return 返回最大公约数
     */
    public static int getGcd(int numOne, int numTwo) {
        //如果不满足题意 m > n
        //执行交换函数
        if (numOne < numTwo) {
            int[] swaps = swap(numOne, numTwo);
            numOne = swaps[0];
            numTwo = swaps[1];
        }
        while (numTwo != 0) {
            int i = numOne % numTwo;
            numOne = numTwo;
            numTwo = i;
        }
        return numOne;
    }

    /**
     * @param numOne 第一个数
     * @param numTwo 第二个数
     * @return 返回最小公倍数
     */
    public static int getLcm(int numOne, int numTwo) {
        return numOne * numTwo / getGcd(numOne, numTwo);
    }

    /**
     * 实现两个 int 类型变量值的交换，
     * 要求不使用中间变量
     * @param numOne 第一个数字
     * @param numTwo 第二个数字
     * @return 返回一个数组接收数字
     */
    public static int[] swap(int numOne, int numTwo) {
        numTwo = numTwo - numOne;
        numOne = numOne + numTwo;
        numTwo = numOne - numTwo;
        return new int[]{numOne, numTwo};
    }


}
